

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="John Doe">
  <meta name="keywords" content="">
  
  <title>背包dp问题 - violet apricity</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10.4.0/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css" />
  



<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"example.com","root":"/","version":"1.8.9","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":0},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null}}};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>violet apricity</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="背包dp问题">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-04-18 15:29" pubdate>
        2021年4月18日 下午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      5.4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      91
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">背包dp问题</h1>
            
            <div class="markdown-body">
              <p>具体见<a target="_blank" rel="noopener" href="https://github.com/tianyicui/pack">背包九讲</a></p>
<h1 id="前导："><a href="#前导：" class="headerlink" title="前导："></a>前导：</h1><p>f-解决方案即状态，v-容量，c-物品体积即费用，w-物品价值，s-物品数量，k-物品类型，d-另一种费用，u-另一个容量</p>
<h1 id="总思路：循环物体-循环容量-循环决策"><a href="#总思路：循环物体-循环容量-循环决策" class="headerlink" title="总思路：循环物体-循环容量-循环决策"></a>总思路：循环物体-循环容量-循环决策</h1><h1 id="初始化问题。"><a href="#初始化问题。" class="headerlink" title="初始化问题。"></a>初始化问题。</h1><p>要求恰好装满背包：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><code class="hljs c++">define fINF=<span class="hljs-number">0x3c3c3c3c</span>  <span class="hljs-comment">//fINF为负无穷</span><br>std::<span class="hljs-built_in">memset</span>(f,fINF,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f)); <span class="hljs-comment">//其他fINF</span><br>f[<span class="hljs-number">0</span>]=<span class="hljs-number">0</span>; <span class="hljs-comment">//首位0</span><br></code></pre></td></tr></table></figure>

<p>不需恰好装满：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs c++">std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br></code></pre></td></tr></table></figure>



<h1 id="01背包"><a href="#01背包" class="headerlink" title="01背包"></a>01背包</h1><p>直接上一维：</p>
<p>sum-前缀和数组，用于常数优化下界。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">//AcWing 01背包 https://www.acwing.com/problem/content/2/</span><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> sum[N],f[N],c[N],w[N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">int</span> n,v;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i];<br>        sum[i]=sum[i<span class="hljs-number">-1</span>]+c[i];<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">int</span> p=std::<span class="hljs-built_in">max</span>((v-sum[n]-sum[i]),c[i]);<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=p;j--)&#123;<br>            f[j]=std::<span class="hljs-built_in">max</span>(f[j],f[j-c[i]]+w[i]);<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    <br>    std::cout&lt;&lt;f[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    <span class="hljs-comment">//SYP</span><br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<h1 id="完全背包"><a href="#完全背包" class="headerlink" title="完全背包"></a>完全背包</h1><p>与01背包的区别在于枚举方向（正向），常数优化不可用</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">//AcWing 完全背包 https://www.acwing.com/problem/content/3/</span><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> n,v;<br><span class="hljs-keyword">int</span> c[N],w[N];<br><span class="hljs-keyword">int</span> f[N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i];<br>    &#125;<br>    <br>    <span class="hljs-comment">//核心</span><br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=c[i];j&lt;=v;j++)&#123;<br>            f[j]=std::<span class="hljs-built_in">max</span>(f[j],f[j-c[i]]+w[i]);<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    <br>    std::cout&lt;&lt;f[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<p>也可以化成01背包求解</p>
<h1 id="多重背包"><a href="#多重背包" class="headerlink" title="多重背包"></a>多重背包</h1><h2 id="二进制优化版本（化为01背包）："><a href="#二进制优化版本（化为01背包）：" class="headerlink" title="二进制优化版本（化为01背包）："></a>二进制优化版本（化为01背包）：</h2><p>将某一物体二进制划分，按位讲其分位多个物体，再采取01背包的方式逐一判断选择。</p>
<p>边读边解版本：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">//	AcWing 多重背包 https://www.acwing.com/problem/content/4/</span><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> n,v;<br><span class="hljs-keyword">int</span> c[N],w[N],s[N];<br><span class="hljs-keyword">int</span> f[N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-comment">//std::cin&gt;&gt;s[i]&gt;&gt;w[i]&gt;&gt;c[i];</span><br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i]&gt;&gt;s[i];<br>    &#125;<br>    <br>    <span class="hljs-comment">//核心</span><br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123; <span class="hljs-comment">//这里还可以优化一下：即先判断够不够多，够多可以直接完全背包，不够分成01背包</span><br>        <span class="hljs-keyword">int</span> k=std::<span class="hljs-built_in">min</span>(s[i],v/c[i]);<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> p=<span class="hljs-number">1</span>;k;p&lt;&lt;=<span class="hljs-number">1</span>)&#123;<br>            <span class="hljs-keyword">if</span>(p&gt;k)p=k;<br>            k-=p;<br>            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=c[i]*p;j--)f[j]=std::<span class="hljs-built_in">max</span>(f[j],f[j-c[i]*p]+w[i]*p);<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    <br>    std::cout&lt;&lt;f[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<p>存下来的版本：</p>
<p>纯用来理解，显然没有第一种优</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> n,v;<br><span class="hljs-keyword">int</span> c[N],w[N],s[N];<br><span class="hljs-keyword">int</span> f[N];<br><span class="hljs-keyword">int</span> newc[N],neww[N];<br><span class="hljs-keyword">int</span> cnt=<span class="hljs-number">0</span>;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i]&gt;&gt;s[i];<br>    &#125;<br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;s[i];j&lt;&lt;=<span class="hljs-number">1</span>)&#123;<br>            <span class="hljs-keyword">if</span>(j&gt;s[i])j=s[i];<br>            cnt++;<br>            newc[cnt]=j*c[i],neww[cnt]=j*w[i];<br>            s[i]-=j;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=cnt;i++)&#123;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=newc[i];j--)&#123;<br>            f[j]=std::<span class="hljs-built_in">max</span>(f[j],f[j-newc[i]]+neww[i]);<br>        &#125;<br>    &#125;<br>    std::cout&lt;&lt;f[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<h2 id="单调队列优化版本："><a href="#单调队列优化版本：" class="headerlink" title="单调队列优化版本："></a>单调队列优化版本：</h2><p>使用单调队列相当于一个滑动窗口，要点在于单调队列的更新和问题的转化。</p>
<p>参见博客：<a target="_blank" rel="noopener" href="https://blog.csdn.net/flyinghearts/article/details/5898183?utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-1.baidujs&amp;dist_request_id=&amp;depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-1.baidujs">https://blog.csdn.net/flyinghearts/article/details/5898183?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.baidujs&amp;dist_request_id=&amp;depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.baidujs</a></p>
<img src="/2021/04/18/PackDP/image1.png" srcset="/img/loading.gif" lazyload class="">

<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">//“多重背包”通用模板</span><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> MAX_V = <span class="hljs-number">100004</span>;<br><span class="hljs-comment">//v、n、w：当前所处理的这类物品的体积、个数、价值</span><br><span class="hljs-comment">//V：背包体积， MAX_V：背包的体积上限值</span><br><span class="hljs-comment">//f[i]：体积为i的背包装前几种物品，能达到的价值上限。</span><br><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pack</span><span class="hljs-params">(<span class="hljs-keyword">int</span> f[], <span class="hljs-keyword">int</span> V, <span class="hljs-keyword">int</span> v, <span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> w)</span></span><br><span class="hljs-function"></span>&#123;<br>  <span class="hljs-keyword">if</span> (n == <span class="hljs-number">0</span> || v == <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span>;<br>  <span class="hljs-keyword">if</span> (n == <span class="hljs-number">1</span>) &#123;               <span class="hljs-comment">//01背包</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = V; i &gt;= v; --i)<br>      <span class="hljs-keyword">if</span> (f[i] &lt; f[i - v] + w) f[i] = f[i - v] + w;<br>    <span class="hljs-keyword">return</span>;<br>  &#125;<br>  <span class="hljs-keyword">if</span> (n * v &gt;= V - v + <span class="hljs-number">1</span>) &#123;   <span class="hljs-comment">//完全背包(n &gt;= V / v)</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = v; i &lt;= V; ++i)<br>      <span class="hljs-keyword">if</span> (f[i] &lt; f[i - v] + w) f[i] = f[i - v] + w;<br>    <span class="hljs-keyword">return</span>;    <br>  &#125;<br><br>  <span class="hljs-keyword">int</span> va[MAX_V], vb[MAX_V];   <span class="hljs-comment">//va/vb: 主/辅助队列</span><br>  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; v; ++j) &#123;     <span class="hljs-comment">//多重背包</span><br>    <span class="hljs-keyword">int</span> *pb = va, *pe = va - <span class="hljs-number">1</span>;     <span class="hljs-comment">//pb/pe分别指向队列首/末元素</span><br>    <span class="hljs-keyword">int</span> *qb = vb, *qe = vb - <span class="hljs-number">1</span>;     <span class="hljs-comment">//qb/qe分别指向辅助队列首/末元素  </span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = j, i = <span class="hljs-number">0</span>; k &lt;= V; k += v, ++i) &#123;<br>      <span class="hljs-keyword">if</span> (pe  == pb + n) &#123;       <span class="hljs-comment">//若队列大小达到指定值，第一个元素X出队。</span><br>        <span class="hljs-keyword">if</span> (*pb == *qb) ++qb;   <span class="hljs-comment">//若辅助队列第一个元素等于X，该元素也出队。 </span><br>        ++pb;<br>      &#125;<br>      <span class="hljs-keyword">int</span> tt = f[k] - i * w;<br>      *++pe = tt;                  <span class="hljs-comment">//元素X进队</span><br>      <span class="hljs-comment">//删除辅助队列所有小于X的元素，qb到qe单调递减，也可以用二分法</span><br>      <span class="hljs-keyword">while</span> (qe &gt;= qb &amp;&amp; *qe &lt; tt) --qe;<br>      *++qe = tt;              <span class="hljs-comment">//元素X也存放入辅助队列        </span><br>      f[k] = *qb + i * w;      <span class="hljs-comment">//辅助队列首元素恒为指定队列所有元素的最大值</span><br>    &#125;<br>  &#125;<br>&#125;<br><br><br></code></pre></td></tr></table></figure>

<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-comment">//AcWing:https://www.acwing.com/problem/content/description/6/</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br>STD<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">20020</span>;<br><span class="hljs-keyword">int</span> n,m;<br><span class="hljs-keyword">int</span> f[N],q[N],g[N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    cin&gt;&gt;n&gt;&gt;m;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)<br>    &#123;<br>        <span class="hljs-keyword">int</span> v,w,s;<br>        cin&gt;&gt;v&gt;&gt;w&gt;&gt;s;<br>        <span class="hljs-built_in">memcpy</span>(g,f,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;v;j++)<br>        &#123;<br>            <span class="hljs-keyword">int</span> hh=<span class="hljs-number">0</span>,tt=<span class="hljs-number">-1</span>;<br>            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=j;k&lt;=m;k+=v)<br>            &#123;<br>                f[k]=g[k];<br>                <span class="hljs-keyword">if</span>(hh&lt;=tt &amp;&amp; k-s*v&gt;q[hh])  <br>                <span class="hljs-comment">//如果当前窗口的内容超过了s个;</span><br>                &#123;<br>                    hh++;<br>                &#125;<br>                <span class="hljs-keyword">if</span>(hh&lt;=tt) <br>                &#123;<br>                    f[k]=<span class="hljs-built_in">max</span>(f[k],g[q[hh]]+(k-q[hh])/v*w); <br>                    <span class="hljs-comment">//max(f[i-1][k],f[i-1][能转移里最大]+个数*v[i]);</span><br>                &#125;<br>                <span class="hljs-keyword">while</span>(hh&lt;=tt &amp;&amp; g[q[tt]]-(q[tt]-j)/v*w &lt;= g[k]-(k-j)/v*w)<br>                &#123;<br>                    tt--;<br>                &#125;<br>                q[++tt]=k;<br>            &#125;<br>        &#125;<br>    &#125;<br>    cout&lt;&lt;f[m]&lt;&lt;endl;<br>&#125;<br></code></pre></td></tr></table></figure>



<h1 id="混合背包"><a href="#混合背包" class="headerlink" title="混合背包"></a>混合背包</h1><p>本质上为前几种背包混合，因此只需要更新f时判断一下k即可</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=N;i++)&#123;<br>    <span class="hljs-keyword">int</span> t=k[i];<br>    <span class="hljs-keyword">if</span>(t==<span class="hljs-number">1</span>)<span class="hljs-built_in">ZeroOnePack</span>(f,c[i],w[i]);<br>    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(t==<span class="hljs-number">2</span>)<span class="hljs-built_in">CompletePack</span>(f,c[i],w[i]);<br>    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(t==<span class="hljs-number">3</span>)<span class="hljs-built_in">MultiplePack</span>(f,c[i],w[i],s[i]);<br>&#125;<br></code></pre></td></tr></table></figure>

<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-comment">//AcWing 混合背包问题 https://www.acwing.com/problem/content/7/</span><br><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">ZeroOnePack</span><span class="hljs-params">(<span class="hljs-keyword">int</span> *f,<span class="hljs-keyword">int</span> c,<span class="hljs-keyword">int</span> w,<span class="hljs-keyword">int</span> v)</span><span class="hljs-comment">//01背包</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=v;i&gt;=c;i--)&#123;<br>        f[i]=std::<span class="hljs-built_in">max</span>(f[i],f[i-c]+w);<br>    &#125;<br>    <span class="hljs-keyword">return</span> ;<br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">CompletePack</span><span class="hljs-params">(<span class="hljs-keyword">int</span> *f,<span class="hljs-keyword">int</span> c,<span class="hljs-keyword">int</span> w,<span class="hljs-keyword">int</span> v)</span><span class="hljs-comment">//完全背包</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=c;i&lt;=v;i++)&#123;<br>        f[i]=std::<span class="hljs-built_in">max</span>(f[i],f[i-c]+w);<br>    &#125;<br>    <span class="hljs-keyword">return</span> ;<br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">MultiplePack</span><span class="hljs-params">(<span class="hljs-keyword">int</span> *f,<span class="hljs-keyword">int</span> c,<span class="hljs-keyword">int</span> w,<span class="hljs-keyword">int</span> s,<span class="hljs-keyword">int</span> v)</span><span class="hljs-comment">//多重背包</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">if</span>(c*s&gt;=v)&#123;<br>        <span class="hljs-comment">//CompletePack(f,c,w,v);</span><br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=c;i&lt;=v;i++)&#123;<br>            f[i]=std::<span class="hljs-built_in">max</span>(f[i],f[i-c]+w);<br>        &#125;<br>        <span class="hljs-keyword">return</span> ;<br>    &#125;<br>    <span class="hljs-keyword">int</span> k=std::<span class="hljs-built_in">min</span>(s,v/c);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> p=<span class="hljs-number">1</span>;k;p&lt;&lt;=<span class="hljs-number">1</span>)&#123;<br>        <span class="hljs-keyword">if</span>(p&gt;k)p=k;<br>        k-=p;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=c*p;j--)f[j]=std::<span class="hljs-built_in">max</span>(f[j],f[j-c*p]+w*p);<br>    &#125;<br>    <span class="hljs-keyword">return</span> ;<br>&#125;<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1011</span>;<br><span class="hljs-keyword">int</span> f[N];<br><span class="hljs-keyword">int</span> w[N],c[N],s[N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">int</span> n;<br>    <span class="hljs-keyword">int</span> v;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i]&gt;&gt;s[i];<br>    &#125;<br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span> f);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">int</span> t=s[i];<br>        <span class="hljs-keyword">if</span>(s[i]==<span class="hljs-number">-1</span>)<span class="hljs-built_in">ZeroOnePack</span>(f,c[i],w[i],v);<span class="hljs-comment">//01背包</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(s[i]==<span class="hljs-number">0</span>)<span class="hljs-built_in">CompletePack</span>(f,c[i],w[i],v);<span class="hljs-comment">//完全背包</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-built_in">MultiplePack</span>(f,c[i],w[i],s[i],v);<span class="hljs-comment">//多重背包</span><br>    &#125;<br>    std::cout&lt;&lt;f[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    SYP<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br><br></code></pre></td></tr></table></figure>



<h1 id="二维费用的背包问题"><a href="#二维费用的背包问题" class="headerlink" title="二维费用的背包问题"></a>二维费用的背包问题</h1><p>费用增加一维，状态也增加一维即 f[i,v,u]=max(f[i-1,v,u],f[i-1,v-c[i],u-d[i]]+w[i]);</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs c++">f[i,v,u]=<span class="hljs-built_in">max</span>(f[i<span class="hljs-number">-1</span>,v,u],f[i<span class="hljs-number">-1</span>,v-c[i],u-d[i]]+w[i]);<br></code></pre></td></tr></table></figure>

<p>二维费用可能以物品最多去几件暗示给出，即件数为另一个费用</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><span class="hljs-comment">//AcWing 二维费用的背包问题 https://www.acwing.com/problem/content/description/8/</span><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> sum[N],sum_[N],f[N][N],c[N],w[N],p[N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">int</span> n,v,m;<br>    std::cin&gt;&gt;n&gt;&gt;v&gt;&gt;m;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;p[i]&gt;&gt;w[i];<br>        sum[i]=sum[i<span class="hljs-number">-1</span>]+c[i];<br>        sum_[i]=sum_[i<span class="hljs-number">-1</span>]+p[i];<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">int</span> d=std::<span class="hljs-built_in">max</span>((v-sum[n]-sum[i]),c[i]);<br>        <span class="hljs-keyword">int</span> l=std::<span class="hljs-built_in">max</span>((m-sum_[n]-sum_[i]),p[i]);<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=d;j--)&#123;<br>            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=m;k&gt;=l;k--)&#123;<br>                f[j][k]=std::<span class="hljs-built_in">max</span>(f[j][k],f[j-c[i]][k-p[i]]+w[i]);<br>            &#125;<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    std::cout&lt;&lt;f[v][m]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    SYP<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br><br></code></pre></td></tr></table></figure>

<h1 id="分组背包"><a href="#分组背包" class="headerlink" title="分组背包"></a>分组背包</h1><p>每组背包物品相互冲突最多只能取一个，那么加上三层循环枚举背包组–状态（v–&gt;0）–该背包内某个物品（1–&gt;s[i]）</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><span class="hljs-comment">//分组背包 AcWing https://www.acwing.com/problem/content/9/</span><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> f[N];<br><span class="hljs-keyword">int</span> s[N];<br><span class="hljs-keyword">int</span> c[N][N];<br><span class="hljs-keyword">int</span> w[N][N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">int</span> n,v,m;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;s[i];<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;=s[i];j++)&#123;<br>            std::cin&gt;&gt;c[i][j]&gt;&gt;w[i][j];<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">//核心</span><br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;  <span class="hljs-comment">//背包分组</span><br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=<span class="hljs-number">0</span>;j--)&#123;  <span class="hljs-comment">//容量</span><br>            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=<span class="hljs-number">1</span>;k&lt;=s[i];k++)&#123;  <span class="hljs-comment">//物品</span><br>                <span class="hljs-keyword">if</span>(j&gt;=c[i][k])f[j]=std::<span class="hljs-built_in">max</span>(f[j],f[j-c[i][k]]+w[i][k]);<br>            &#125;<br>        &#125;<br>    &#125;<br>    std::cout&lt;&lt;f[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    SYP<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br><br></code></pre></td></tr></table></figure>

<h1 id="有依赖的背包问题"><a href="#有依赖的背包问题" class="headerlink" title="有依赖的背包问题"></a>有依赖的背包问题</h1><p>物品之间存在依赖关系，即选择吗，某个物体必须选择另一个物体。类似于一棵树，<strong>选择子节点必须先选择父节点</strong>。也可以这么想，每个主件都有附件，每个附件也可能是一个主件，每次选择一个整体，即<strong>主件和属于它的若干个附件</strong>。那么在这里可以将其化为<strong>分组背包</strong>。</p>
<p>实际上这也是个<strong>树上dp问题</strong>具体解决方案为：1.画出一棵树，2.dfs[root]，对节点至上而下深搜，对于每个状态当前节点选择之后往下更新，枚举子树分到的容量。</p>
<p>这里用邻接表画树。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><span class="hljs-comment">//AcWing:https://www.acwing.com/problem/content/description/10/</span><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> n,v,root;<br><span class="hljs-keyword">int</span> f[N][N];<br><span class="hljs-keyword">int</span> c[N],w[N];<br><span class="hljs-keyword">int</span> h[N];<span class="hljs-comment">//邻接表的头，下标为节点标号，权值为当前节点最后加入的边的标号</span><br><span class="hljs-keyword">int</span> ne[N];<span class="hljs-comment">//nextedge，下标为节点标号，-1表示没有下一条边，权值为当前节点下一条边的标号</span><br><span class="hljs-keyword">int</span> e[N];<span class="hljs-comment">//边的集合，下标是边的标号，权值是当前边的终点</span><br><span class="hljs-keyword">int</span> cnt;<span class="hljs-comment">//保存每条边的上一条边的标号</span><br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b)</span><span class="hljs-comment">//邻接表加边操作，仔细体会</span></span><br><span class="hljs-function"></span>&#123; <span class="hljs-comment">//上一条边终点为b 上一条边的下一条边为当前边 更新起点为a的边</span><br>    e[cnt]=b,ne[cnt]=h[a],h[a]=cnt++;<span class="hljs-comment">//加入边a-b更新cnt++即为下一条边</span><br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">int</span> u)</span><span class="hljs-comment">//深搜一下</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=h[u];i!=<span class="hljs-number">-1</span>;i=ne[i])<span class="hljs-comment">//遍历当前节点的边</span><br>    &#123;<br>        <span class="hljs-keyword">int</span> son=e[i];<span class="hljs-comment">//当前边的终点，即子节点</span><br>        <span class="hljs-built_in">dfs</span>(son);<span class="hljs-comment">//先往下，对子节点深搜</span><br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v-c[u];j&gt;=<span class="hljs-number">0</span>;j--)&#123;<br>            <span class="hljs-comment">//遍历背包的容量，注意当前节点表示的物体是必选的，因此先处理</span><br>            <span class="hljs-comment">//此时当前节点可看作一个背包组，子节点的每种选择看作是组里的一个物体，所以要大到小遍历</span><br>            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=<span class="hljs-number">0</span>;k&lt;=j;k++)&#123;<span class="hljs-comment">//遍历子节点的组合</span><br>                f[u][j]=std::<span class="hljs-built_in">max</span>(f[u][j],f[u][j-k]+f[son][k]);<span class="hljs-comment">//因为前面已经dfs所以默认son的情况已经计算好了</span><br>            &#125;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=v;i&gt;=c[u];i--)f[u][i]=f[u][i-c[u]]+w[u];<span class="hljs-comment">//加上默认选择的当前节点物体u</span><br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;c[u];i++)f[u][i]=<span class="hljs-number">0</span>;<span class="hljs-comment">//对于容量小于当前物体费用的，即放不下的情况，需要置0</span><br>    <span class="hljs-keyword">return</span> ;<br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span> f);<br>    std::<span class="hljs-built_in">memset</span>(h,<span class="hljs-number">-1</span>,<span class="hljs-keyword">sizeof</span> h);<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">int</span> p;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i]&gt;&gt;p;<br>        <span class="hljs-keyword">if</span>(p==<span class="hljs-number">-1</span>)&#123;root=i;&#125;<br>        <span class="hljs-keyword">else</span> <span class="hljs-built_in">add</span>(p,i);<br>    &#125;<br>    <span class="hljs-built_in">dfs</span>(root);<span class="hljs-comment">//从根节点开始dfs</span><br>    std::cout&lt;&lt;f[root][v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    SYP<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<p><strong>/<em>金明的预算方案</em>/</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;cstdio&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> std;<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxn = <span class="hljs-number">64</span>;<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxm = maxn;<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxv = <span class="hljs-number">33333</span>;<br><span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">Node</span>&#123;</span><span class="hljs-comment">//表示物品</span><br>    <span class="hljs-keyword">int</span> v,w;<br>    <span class="hljs-built_in">Node</span>() = <span class="hljs-keyword">default</span>;<br>    <span class="hljs-built_in">Node</span>(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b):<span class="hljs-built_in">v</span>(a),<span class="hljs-built_in">w</span>(b)&#123;&#125;<br>&#125;d[maxn],t[maxn];<br><span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">Edge</span>&#123;</span><br>    <span class="hljs-keyword">int</span> from,to;<br>    <span class="hljs-built_in">Edge</span>() = <span class="hljs-keyword">default</span>;<br>    <span class="hljs-built_in">Edge</span>(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b):<span class="hljs-built_in">from</span>(a),<span class="hljs-built_in">to</span>(b)&#123;&#125;<br>&#125;Edges[maxm];<br><span class="hljs-keyword">int</span> head[maxn],nxt[maxm],root[maxn],rp;<br><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addedge</span><span class="hljs-params">(<span class="hljs-keyword">int</span> from,<span class="hljs-keyword">int</span> to)</span></span>&#123;<br>    <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> tot;<br>    Edges[++tot] = <span class="hljs-built_in">Edge</span>(from,to);<br>    nxt[tot] = head[from];<br>    head[from] = tot;<br>&#125;<br><span class="hljs-keyword">int</span> pre[maxn],f[maxn][maxv],p = <span class="hljs-number">0</span>;<br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">int</span> u)</span></span>&#123;<br>    <span class="hljs-keyword">int</span> tp = p;<span class="hljs-comment">//由于后序遍历的性质,一个点的左兄弟显然是进入这个点时序列中的最后一个点</span><br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[u];i;i = nxt[i])&#123;<br>        Edge &amp;e = Edges[i];<br>        <span class="hljs-built_in">dfs</span>(e.to);<br>    &#125;<br>    d[++p] = t[u];<span class="hljs-comment">//后序遍历</span><br>    pre[p] = tp;<span class="hljs-comment">//求左兄弟,注意,pre[t]表示序列中编号为t的节点的左兄弟的编号</span><br>&#125;<br><span class="hljs-keyword">int</span> n,m;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;<br><span class="hljs-meta">#<span class="hljs-meta-keyword">ifdef</span> LOCAL</span><br>    <span class="hljs-built_in">freopen</span>(<span class="hljs-string">&quot;fafa.in&quot;</span>,<span class="hljs-string">&quot;r&quot;</span>,stdin);<br><span class="hljs-meta">#<span class="hljs-meta-keyword">endif</span></span><br>    <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%d %d&quot;</span>,&amp;m,&amp;n);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;i++)&#123;<span class="hljs-comment">//建图</span><br>        <span class="hljs-keyword">int</span> v,w,faz;<br>        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%d %d %d&quot;</span>,&amp;v,&amp;w,&amp;faz);<br>        t[i] = <span class="hljs-built_in">Node</span>(v,v * w);<span class="hljs-comment">//先预处理它的权值</span><br>        <span class="hljs-built_in">addedge</span>(faz,i);<span class="hljs-comment">//有个技巧,如果一个点是主件,我们就认为它依赖于虚拟点0</span><br>    &#125;<br>    <span class="hljs-built_in">dfs</span>(<span class="hljs-number">0</span>);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;i++)<span class="hljs-comment">//dp求解</span><br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>;j &lt;= m;j++)<br>            <span class="hljs-keyword">if</span>(j &gt;= d[i].v)f[i][j] = <span class="hljs-built_in">max</span>(f[pre[i]][j],f[i - <span class="hljs-number">1</span>][j - d[i].v] + d[i].w);<br>            <span class="hljs-keyword">else</span> f[i][j] = f[pre[i]][j];<span class="hljs-comment">//转移 </span><br>    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%d\n&quot;</span>,f[n][m]);<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br><br></code></pre></td></tr></table></figure>

<h1 id="其他问法"><a href="#其他问法" class="headerlink" title="其他问法"></a>其他问法</h1><h2 id="求方案总数"><a href="#求方案总数" class="headerlink" title="求方案总数"></a>求方案总数</h2><p>因为状态转移的时候已经把所有方案搜过了,因此可以将max取大改为sum取和，初始条件是f[0,0]=1。即：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs c++">f[i,v]=sum&#123;f[i<span class="hljs-number">-1</span>,v],f[i,v-ci]&#125;<br></code></pre></td></tr></table></figure>

<h2 id="求最优方案数"><a href="#求最优方案数" class="headerlink" title="求最优方案数"></a>求最优方案数</h2><p>这里的最优方案数指是价值最大的方案总数。</p>
<p>以01背包为例，对每个物体有两种选择方案，那么当前方案总数即应该加上其中合理的方案，可能会同时合理，因此答案就会增加而不是永1。    由于01背包可以边读边解决，不需要存下来，这里可以把方案数全置1，判断选不选的价值，若相同则可以跟新当前为两者的和，否则继承上一个状态。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> n,v,root;<br><span class="hljs-keyword">int</span> f[N],g[N];<br><span class="hljs-keyword">int</span> c[N],w[N];<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> mod=<span class="hljs-number">1e9</span>+<span class="hljs-number">7</span>;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span> f);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;=v;i++)g[i]=<span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">int</span> a,b;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;a&gt;&gt;b;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=a;j--)&#123;<br>            <span class="hljs-keyword">int</span> t=f[j-a]+b;<br>            <span class="hljs-keyword">if</span>(t&gt;f[j])f[j]=t,g[j]=g[j-a];<br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(t==f[j])g[j]=(g[j]+g[j-a])%mod;<br>        &#125;<br>    &#125;<br>    std::cout&lt;&lt;g[v]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br><br><br></code></pre></td></tr></table></figure>

<h2 id="输出字典序最小的最优方案"><a href="#输出字典序最小的最优方案" class="headerlink" title="输出字典序最小的最优方案"></a>输出字典序最小的最优方案</h2><p>把物体遍历的方向改变一下，从n到1遍历，这样子先判断的物体序号更大输出更靠后。</p>
<p>或者可以将答案存入数组排序后输出，不过时间和空间消耗的都更多。</p>
<p>或许很朴素的从小到大遍历物体，判断选择情况再输出，这样子可以做到在选与不选价值一样时先选择字典序最小的。</p>
<p>PS：如果不要求字典序最小，解法当然也知道了。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> f[N][N],c[N],w[N],g[N][N];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">int</span> n,v;<br>    std::cin&gt;&gt;n&gt;&gt;v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i];<br>    &#125;<br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=n;i&gt;=<span class="hljs-number">1</span>;i--)&#123;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;=v;j++)&#123;<br>            f[i][j]=f[i+<span class="hljs-number">1</span>][j];<br>            <span class="hljs-keyword">if</span>(j&gt;=c[i])&#123;<br>                f[i][j]=std::<span class="hljs-built_in">max</span>(f[i][j],f[i+<span class="hljs-number">1</span>][j-c[i]]+w[i]);<br>            &#125;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">int</span> cnt=v;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">if</span>(i==n&amp;&amp;cnt&gt;=c[i])&#123;std::cout&lt;&lt;i&lt;&lt;<span class="hljs-string">&#x27; &#x27;</span>;<span class="hljs-keyword">break</span>;&#125;<span class="hljs-comment">//物体选完了记得break</span><br>        <span class="hljs-keyword">if</span>(cnt&lt;=<span class="hljs-number">0</span>)<span class="hljs-keyword">break</span>;<span class="hljs-comment">//装不下了break</span><br>        <span class="hljs-keyword">if</span>(cnt&gt;=c[i]&amp;&amp;f[i][cnt]==f[i+<span class="hljs-number">1</span>][cnt-c[i]]+w[i])&#123;<br>            std::cout&lt;&lt;i&lt;&lt;<span class="hljs-string">&#x27; &#x27;</span>;cnt-=c[i];<br>        &#125;<br>    &#125;<br>    <span class="hljs-built_in">puts</span>(<span class="hljs-string">&quot;&quot;</span>);<br>    SYP<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<h2 id="k优解问题"><a href="#k优解问题" class="headerlink" title="k优解问题"></a>k优解问题</h2><p>多了一层维度k，解决方案多加一层维度，即f[i,v]—&gt;f[i,v,1….k]，显然这k个数应该是有序队列。</p>
<p>状态转移：f[i,v]由f[i-1,v]和f[i-1,v-ci]+wi这<strong>两个有序队列合并</strong>而来，前者即f[i, v,1…..k]，而后者由f[i-1,v-ci,1…k]这个队列每个数加上wi得到。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><code class="hljs c++">        <span class="hljs-comment">// violet apricity</span><br><span class="hljs-comment">// Do all I can do.Do good to be good.</span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;stdio.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;string&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;math.h&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;sstream&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iomanip&gt;</span></span><br><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> STD using namespace std;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ll long long</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> db double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ldb long double</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IS std::ios::sync_with_stdio(false),std::cin.tie(0);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAX 88888888</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> INF 0x3f3f3f3f</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> r0 return 0;</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> SYP system(<span class="hljs-meta-string">&quot;pause&quot;</span>);</span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> endl <span class="hljs-meta-string">&#x27;\n&#x27;</span></span><br><br><br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N=<span class="hljs-number">1005</span>;<br><span class="hljs-keyword">int</span> f[N][<span class="hljs-number">55</span>],c[N],w[N],g[N][N];<br><span class="hljs-keyword">int</span> a[<span class="hljs-number">55</span>],b[<span class="hljs-number">55</span>];<br><span class="hljs-keyword">int</span> d;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-keyword">int</span> n,v,k;<br>    std::cin&gt;&gt;n&gt;&gt;v&gt;&gt;k;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        std::cin&gt;&gt;c[i]&gt;&gt;w[i];<br>    &#125;<br>    std::<span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-built_in"><span class="hljs-keyword">sizeof</span></span>(f));<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=v;j&gt;=c[i];j--)&#123;<br>            <span class="hljs-keyword">for</span>(d=<span class="hljs-number">1</span>;d&lt;=k;d++)&#123;<br>                a[d]=f[j-c[i]][d]+w[i];<br>                b[d]=f[j][d];<br>            &#125;<br>            a[d]=b[d]=<span class="hljs-number">-1</span>;<br>            <span class="hljs-keyword">int</span> x=<span class="hljs-number">1</span>,y=<span class="hljs-number">1</span>,z=<span class="hljs-number">1</span>;<br>            <span class="hljs-keyword">while</span>(z&lt;=k&amp;&amp;(x&lt;=k||y&lt;=k))&#123;<br>                <span class="hljs-keyword">if</span>(a[x]&gt;b[y])f[j][z]=a[x++];<span class="hljs-comment">//选</span><br>                <span class="hljs-keyword">else</span> f[j][z]=b[y++];<span class="hljs-comment">//不选</span><br>                <span class="hljs-keyword">if</span>(f[j][z]!=f[j][z<span class="hljs-number">-1</span>])z++;<span class="hljs-comment">//更新</span><br>            &#125;<br>        &#125;<br>    &#125;<br>    std::cout&lt;&lt;f[v][k]&lt;&lt;<span class="hljs-string">&#x27;\n&#x27;</span>;<br>    SYP<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<br></code></pre></td></tr></table></figure>


            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/ACM/">ACM</a>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95Algorithm/">算法Algorithm</a>
                    
                      <a class="hover-with-bg" href="/tags/DP/">DP</a>
                    
                      <a class="hover-with-bg" href="/tags/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/">背包问题</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/04/18/Recursion/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">递归</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2021/04/17/Codeforces-Round-715-Div-2-2021-04-16/">
                        <span class="hidden-mobile">CFR715(Div.2)2021.04.16</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>Fluid</span></a> 
  </div>
  

  

  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  <script  src="https://cdn.jsdelivr.net/npm/tocbot@4.12.0/dist/tocbot.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4.3.0/anchor.min.js" ></script>



  <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js" ></script>






  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2.0.11/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
      typing(title)
      
    })(window, document);
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    (function () {
      var path = "/local-search.xml";
      $('#local-search-input').on('click', function() {
        searchFunc(path, 'local-search-input', 'local-search-result');
      });
      $('#modalSearch').on('shown.bs.modal', function() {
        $('#local-search-input').focus();
      });
    })()
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
